#define _CRT_SECURE_NO_WANINGS 1
#pragma warning(disable: 4996)
typedef int QeDataType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QeDataType data;
}Qnode;
typedef struct Queue
{
	Qnode* head;
	Qnode* back;
}Qe;
Qnode* CreateNode(QeDataType x)
{
	Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void QueueInit(Qe* q)
{
	assert(q);
	Qnode* newnode = CreateNode(-1);
	q->head = newnode;
	q->back = newnode;
}
void QueueDestroy(Qe* q)
{
	assert(q);
	Qnode* cur = q->head->next;
	while (cur)
	{
		Qnode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->back = NULL;
	free(q->head);
	q->head = NULL;
}
void Queuepush(Qe* q, QeDataType x)
{
	assert(q);
	Qnode* newnode = CreateNode(x);
	q->back->next = newnode;
	q->back = newnode;
}
void QueuePop(Qe* q)
{
	assert(q);
	assert(q->head->next);

	Qnode* next = q->head->next;
	q->head->next = next->next;
	free(next);
	next = NULL;
	if (q->head->next == NULL)
	{
		q->back = q->head;
		q->back->next = NULL;
	}
}
QeDataType QueueFront(Qe* q)
{
	assert(q);
	assert(q->head->next);
	return q->head->next->data;
}
QeDataType QueueBack(Qe* q)
{
	assert(q);
	assert(q->head->next);
	return q->back->data;
}
int QueueSize(Qe* q)
{
	Qnode* size = q->head->next;
	int num = 0;
	while (size)
	{
		size = size->next;
		num++;
	}
	return num;
}
bool QueueEmpty(Qe* q)
{
	return q->head->next == NULL;
}


typedef struct {
	Qe q1;
	Qe q2;
} MyStack;


MyStack* myStackCreate() {
	MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
	QueueInit(&pst->q1);
	QueueInit(&pst->q2);
	return pst;
}

void myStackPush(MyStack* obj, int x) {
	if (!QueueEmpty(&obj->q1))
	{
		Queuepush(&obj->q1, x);
	}
	else
	{
		Queuepush(&obj->q2, x);
	}
}

int myStackPop(MyStack* obj) {
	Qe* unemptyQe = &obj->q2;
	Qe* emptyQe = &obj->q1;
	if (!QueueEmpty(&obj->q1))
	{
		unemptyQe = &obj->q1;
		emptyQe = &obj->q2;
	}
	while (QueueSize(unemptyQe) > 1)
	{
		Queuepush(emptyQe, QueueFront(unemptyQe));
		QueuePop(unemptyQe);
	}
	int unemptyQedata = QueueFront(unemptyQe);
	QueuePop(unemptyQe);
	return unemptyQedata;
}

int myStackTop(MyStack* obj) {
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}

bool myStackEmpty(MyStack* obj) {
	if (QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2))
	{
		return true;
	}
	else
	{
		return false;
	}
}

void myStackFree(MyStack* obj) {
	if (!QueueEmpty(&obj->q1))
	{
		QueueDestroy(&obj->q1);
	}
	if (!QueueEmpty(&obj->q2))
	{
		QueueDestroy(&obj->q2);
	}
	free(obj);

}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);

 * int param_2 = myStackPop(obj);

 * int param_3 = myStackTop(obj);

 * bool param_4 = myStackEmpty(obj);

 * myStackFree(obj);
*/